import java.util.Arrays;

public class BBSD {
    //给定一个整数数组nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
    // 例如：nums = [4, 3, 2, 3, 5, 2, 1], k = 4  可以将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和
    public boolean canDivide(int[] nums,int k) {
        //因为是将这个数组刚好分成K组，若这个数组的总和不能整除K那么将不可能分组
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % k != 0) return false;
        //若这个数组中的最大数字大于平均值则无法分组成功
        Arrays.sort(nums);
        int num = sum / k;
        if (num < nums[n - 1]) return false;
        //能整除则有可能可以分组成功
        //创建一个长度为k的数组，每个数位大小为平均数，递归遍历看看能否用数组中的数将其填满
        int[] arr = new int[k];
        Arrays.fill(arr,num);
        return divide(nums,n,arr,k);
    }
    //分组过程,将原数组中的数从后往前依次放入arr中
    private boolean divide(int[] nums, int n, int[] arr, int k) {
        if (n < 0) {
            //已经将nums中的数都放入到了arr中
            return true;
        }
        //arr数组从0到k - 1的位置挨个放入元素
        for (int i = 0; i < k; i++) {
            //当前元素刚好能填满当前位置或者放入了之后还能放下值小一些的元素，则继续递归
            if (arr[i] == nums[n] || (arr[i] - nums[n] >= nums[0])) {
                arr[i] -= nums[n];
                if (divide(nums,n - 1,arr,k)) return true;
                //这个元素放错位置了,将其拿出放入其他位置
                arr[i] += nums[n];
            }
        }
        //尝试了所有的防止方法都没有分组完成则返回false
        return false;
    }
}
